package com.sourcetrip.my;

import com.sourcetrip.my.abs.AbstractHeap;
import com.sourcetrip.utils.printer.BinaryTreeInfo;

/**
 * @author: ZhouBert
 * @date: 2020/12/25
 * @description: 二叉堆（大顶堆） 设计：
 * 从本质上来说，二叉堆是由二叉树实现的。但是由于二叉堆需要的是【完全二叉树】，
 * 完全二叉树有个规律：编个索引，可以从当前节点 <-> 父节点，双向。
 * 既然有了这个规律，就可以用 【数组】来实现，这样节省了很多的空间。
 * 杀鸡焉用牛刀。
 * --
 * 首先自己实现 数组实现的（假设不存在相同的元素，如果要考虑等事先比较一番，那就需要 O(n)的复杂度）
 * 分析：
 * 1.add()：添加完元素后，进行调整，将该元素与父元素进行比较，直到根节点；
 * 添加需要考虑扩容，本版本不做缩容考虑。
 * 2.remove():删除堆顶元素。想法很巧妙！按照原本的想法，通过堆顶元素的删除，然后将下面的元素一个个上溢，
 * 这样会造成最后一层不满足完全二叉树的条件，如果再将最后一层的元素进行移动，就非常麻烦。（没有朴实的规律，只有暴力解法）
 * 于是，将最后的节点放在堆顶，再通过调整，就能让最后调整完的结果符合完全二叉树！
 */
public class BinaryHeapV0<E> extends AbstractHeap<E> implements BinaryTreeInfo {

	private int DEFAULT_CAPACITY = 10;

	/**
	 * 由于没办法 new E[]，只能如此，似乎跟 Object[] 差不多？
	 */
	E[] array = (E[]) new Object[DEFAULT_CAPACITY];

	//region	constructor

//	public BinaryHeapV0(E[] elements, Comparator<E> comparator)  {
//		super(comparator);
//
//		if (elements == null || elements.length == 0) {
//			this.array = (E[]) new Object[DEFAULT_CAPACITY];
//		} else {
//			size = elements.length;
//			int capacity = Math.max(elements.length, DEFAULT_CAPACITY);
//			this.array = (E[]) new Object[capacity];
//			for (int i = 0; i < elements.length; i++) {
//				this.array[i] = elements[i];
//			}
//			heapify();
//		}
//	}
//
//	public BinaryHeapV0(E[] elements)  {
//		this(elements, null);
//	}

	//endregion


	@Override
	public void clear() {
		array = (E[]) new Object[DEFAULT_CAPACITY];
		size = 0;
	}


	/**
	 * 往堆中添加元素，并进行调整，满足父节点一直大于两个子节点。
	 *
	 * @param element
	 */
	@Override
	public void add(E element) {
		//马上溢出（没有考虑并发）
		if (size == array.length) {
			int nLen = size + (size >> 1);
			E[] tempArr = (E[]) new Object[nLen];
			//copy
			System.arraycopy(array, 0, tempArr, 0, size);
			//reset reference
			array = tempArr;
		}
		//add new item
		//TODO:(-1) >> 1 == -1;(1) >> 1 == 0
		array[size] = element;
		int childIndex = size;
		int parentIndex = (childIndex - 1) >> 1;
		while (parentIndex >= 0) {
			//当 parent < child ,shift up
			int compareRes = compare(array[parentIndex], array[childIndex]);
			if (compareRes < 0) {
				//交换
				swap(parentIndex, childIndex);
				//迭代参数
				childIndex = parentIndex;
				parentIndex = (childIndex - 1) >> 1;
			} else if (compareRes == 0) {
				//相等就抛出异常--其实就算一条线上不会碰到相等的元素，在另一条线上也可能相等
				throw new IllegalArgumentException("二叉堆中不允许相等的元素");
			} else {
				break;
			}
		}
		size++;
	}


	/**
	 * 返回堆顶元素（max item）
	 *
	 * @return
	 */
	@Override
	public E get() {
		rangeCheck(0);
		return array[0];
	}

	/**
	 * 移除堆顶元素
	 * TODO:很巧妙的思路：将堆顶元素移除后，再将 最后的元素添加到堆顶，然后向下调整！
	 *
	 * @return
	 */
	@Override
	public E remove() {
		rangeCheck(0);
		E oldValue = array[0];
		//进行调整
		array[0] = array[--size];




		return oldValue;
	}

	/**
	 * 删除堆顶元素的同时插入一个新元素
	 * 这个跟 remove() 有相同的调整逻辑
	 *
	 * @param element
	 * @return old value
	 */
	@Override
	public E replace(E element) {
		rangeCheck(0);
		E oldValue = array[0];
		//执行替代
		array[0] = element;
		//调整
		afterRemove();


		return oldValue;
	}


	//region	private methods

	/**
	 * 直接交换数组中 parentIndex 和 childIndex 的元素
	 *
	 * @param parentIndex
	 * @param childIndex
	 */
	private void swap(int parentIndex, int childIndex) {
		E tempItem = array[parentIndex];
		array[parentIndex] = array[childIndex];
		array[childIndex] = tempItem;
	}

	/**
	 * 删除元素之后的调整（size 已经是现实个数）
	 */
	private void afterRemove(){
		int parentIndex = 0;
		int leftChildIndex = (parentIndex << 1) + 1;
		//int rightChildIndex = (parentIndex << 1) + 2;
		int rightChildIndex = leftChildIndex + 1;
		int swapIndex = 0;
		int compareRes = 0;
		while (leftChildIndex < size) {
			//先进行 左比较，如果 left 大于 parent -> swap
			//再进行 右比较，如果 right 大于 parent -> swap
			//思考了一下，上面这个 swap 方式是盲目的，会导致后续的处理十分繁杂。应该是这样的，每一次都跟左右子树中最大的进行交换即可
			if (rightChildIndex < size) {
				//存在 右子节点
				compareRes = compare(array[leftChildIndex], array[rightChildIndex]);
				if (compareRes == 0) {
					throw new IllegalArgumentException("二叉堆中不允许相等的元素");
				}
				if (compareRes > 0) {
					swapIndex = leftChildIndex;
				} else {
					swapIndex = rightChildIndex;
				}
			} else {
				//不存在 右子节点
				swapIndex = leftChildIndex;
			}
			//然后只需要将 parentIndex 与 swapIndex 进行比较即可
			compareRes = compare(array[parentIndex], array[swapIndex]);
			if (compareRes == 0) {
				throw new IllegalArgumentException("二叉堆中不允许相等的元素");
			}
			if (compareRes > 0) {
				//parent > 最大的左子树时，说明已经符合了
				break;
			} else {
				//进入下一轮循环
				swap(parentIndex, swapIndex);

				parentIndex = swapIndex;
				leftChildIndex = (parentIndex << 1) + 1;
				rightChildIndex = leftChildIndex + 1;
			}
		}
	}

	//endregion

	public static void main(String[] args) {
		int i = (-1) >> 1;
		int j = (1) >> 1;
		System.out.println("i = " + i);
		System.out.println("j = " + j);
	}


	//region	BinaryTreeInfo implements

	/**
	 * 找到节点的右节点
	 *
	 * @param node
	 * @return
	 */
	@Override
	public Object right(Object node) {
		int index = ((int) node << 1) + 2;
		return index >= size ? null : index;
	}

	@Override
	public Object root() {
		return 0;
	}

	@Override
	public Object left(Object node) {
		int index = ((int) node << 1) + 1;
		return index >= size ? null : index;
	}

	@Override
	public Object string(Object node) {
		return array[(int) node];
	}


	//endregion

}
